package com.kabuda.zhugehot200;

/**
 * @author kabuda
 * @date 2025-03-24 20:54
 * @description
 */
public class t198_打家劫舍 {
    public static void main(String[] args) {
        System.out.println(rob(new int[]{1, 2, 3, 1}));
        System.out.println(rob2(new int[]{1, 2, 3, 1}));
        System.out.println(rob3(new int[]{1, 0}));
    }

    public static int rob(int[] nums) {
        return dfs(nums, nums.length - 1);
    }

    /**
     * 深度优先递归
     *
     * @param nums
     * @param index
     * @return
     */
    public static int dfs(int[] nums, int index) {
        if (nums == null || index < 0) {
            return 0;
        }
        if (index == 0) {
            return nums[0];
        }

        return Math.max(dfs(nums, index - 1), dfs(nums, index - 2) + nums[index]);
    }


    /**
     * 动态规划:从前往后去推导
     *
     * @param nums
     * @return
     */
    public static int rob2(int[] nums) {
        int length = nums.length;
        if (nums == null || length == 0) {
            return 0;
        }
        if (length == 1) {
            return nums[0];
        }

        //初始化
        int first = nums[0];
        int second = Math.max(nums[0], nums[1]);

        for (int i = 2; i < length; i++) {
            int temp = Math.max(second, first + nums[i]);
            first = second;
            second = temp;
        }
        return second;
    }


    /**
     * 首尾相连，那我们比较取首部的最大值，和取尾部的最大值即可
     *
     * @param nums
     * @return
     */
    public static int rob3(int[] nums) {
        return Math.max(maxMoney(nums, 0, nums.length - 1), maxMoney(nums, 1, nums.length));
    }


    /**
     * @param nums
     * @param start
     * @param end
     * @return
     */
    public static int maxMoney(int[] nums, int start, int end) {
        int length = nums.length;
        if (nums == null || length == 0) {
            return 0;
        }
        if (length == 1) {
            return nums[0];
        }

        //初始化
        int first = nums[start];

        int second;
        if (start + 1 >= end) {
            return first;
        } else {
            second = Math.max(nums[start], nums[start + 1]);
        }

        for (int i = start + 2; i < end; i++) {
            int temp = Math.max(second, first + nums[i]);
            first = second;
            second = temp;
        }
        return second;
    }

}
